package jzoffer;

import leetcode.tree.TreeNode;

import java.util.*;

/**
 * @author MaoLin Wang
 * @date 2020/10/10 11:12 上午
 */
public class _34二叉树中和为某一值的所有路径 {
    static LinkedList<Integer>path=new LinkedList<>();

    public static List<List<Integer>> pathSum(TreeNode root, int sum) {
        if(root==null){
            return new ArrayList<>();
        }
        List<List<Integer>>res=new ArrayList<>();

        dfs(res,sum,root);
        return res;
    }

    private static void dfs(List<List<Integer>> res, int sum,TreeNode root) {
        if (root==null){
            return;
        }
        path.add(root.val);
        sum-=root.val;
        if (sum==0 && root.left==null && root.right==null){
            res.add(new ArrayList<>(path));
        }
        dfs(res, sum, root.left);
        dfs(res, sum, root.right);
        path.removeLast();
    }

    public static void main(String[] args) {
        TreeNode treeNode=new TreeNode(1);
        treeNode.left=new TreeNode(2);
        treeNode.right=new TreeNode(3);
        treeNode.left.left=new TreeNode(4);
        treeNode.left.right=new TreeNode(5);
        List<List<Integer>> lists = pathSum(treeNode, 8);
        System.out.println(lists);
    }
}
